//如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，
// 那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，
// 那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流
// ，使用GetMedian()方法获取当前读取数据的中位数。
import java.util.ArrayList;
import java.util.List;
//输入 [5,2,3,4,1,6,7,0,8]
//返回:" 5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "

//思路
// step 1：用一数组存储输入的数据流。
//step 2：Insert函数在插入的同时，遍历之前存储在数组中的数据，按照递增顺序依次插入，如此一来，加入的数据流便是有序的。
//step 3：GetMedian函数可以根据下标直接访问中位数，分为数组为奇数个元素和偶数个元素两种情况。记得需要类型转换为double。


public class Solution {
    ArrayList<Integer>  list= new ArrayList<>();

    public void Insert(Integer num) {
        if(list.isEmpty()){
            list.add(num);
        }else{
            //Insert函数插入的时候遍历之前在数组的数据，按照递增顺序插入，使得数据有序
            int i=0;
            //遍历找到插入点
            for(; i < list.size(); i++){
                if(num <= list.get(i))
                    break;
            }
            //插入相应位置
            list.add(i, num);
        }

    }

    public Double GetMedian() {
        int n = list.size();
        //奇数个数字
        if(n % 2 == 1)
            //类型转换
            return (double)list.get(n / 2);
            //偶数个数字
        else{
            double a = list.get(n / 2);
            double b = list.get(n / 2 - 1);
            return (a + b) / 2;
        }
    }


}
